package q279_numSquares;

import java.util.Arrays;

public class Solution {
    /**
     * 仍然是完全背包问题，但是这次的物品相对比较特殊
     */
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        // n_squares代表我们能够使用的最大的平方数的开方值
        // 也就是说 我们所使用的物品只能够从这些数的平方中取
        int n_squares = (int) Math.sqrt(n);

        // 接下来就是标准的完全背包
        for (int i = 1; i <= n_squares; i++) { // 遍历物品
            for (int j = i; j <= n; j++) { // 遍历背包
                if (j >= i * i && dp[j - i * i] != Integer.MAX_VALUE) {
                    // 注意
                    // 1 递推公式有所不同 原来的是 j - i 这里是减去平方数
                    // 2 判断的时候要判断 j - i * i 是不是就是初始值 如果是的话 则不进行判断 否则会出现溢出
                    dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
                }

            }
        }

        return dp[n];
    }
}
